package com.cty.seventhDay;

import java.util.HashMap;
import java.util.HashSet;

/*
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度
 * */
public class Q_8 {
    public static void main(String[] args) {
        String s = "pwwkew";
        int i = lengthOfLongestSubstring(s);
        System.out.println(i);
    }

    // 滑动窗口 使用滑动窗口 先记录一下开始的索引 用一个散列表记录一下相同字符出现的位置然后考虑 滑动窗口的缩小大小
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int n = s.length(), currentLength = 0, maxLength = 0, startIndex = 0;
        for (int i = 0; i < n; i++) {
            //如果散列表中不存在该字符传入
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), i);
                currentLength++;
            } else {
                if (currentLength > maxLength) {
                    //更新最大长度
                    maxLength = currentLength;
                }
                //将起始索引更新 判断该字母出现的位置是否在滑动窗口的范围内
                startIndex = Math.max(map.get(s.charAt(i)),startIndex);
                //更新散列表中字符的位置
                map.put(s.charAt(i), i);
                //更新当前滑动窗口的长度
                currentLength = i - startIndex;
            }
        }
        if (currentLength > maxLength) {
            maxLength = currentLength;
        }
        return maxLength;
    }
}
